package demo;

public class Sort {
    public static void insertSort(int[] arr, int begin, int end) {
        for(int i = begin+1; i<=end; i++) {
            int j = i-1;
            int tmp = arr[i];
            for(; j>=begin; j--) {
                if(arr[j] > tmp) {
                   arr[j+1] = arr[j];
                }else {
                   break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    public static void shellSort(int[] arr, int begin, int end) {
        int gap = end-begin+1;
        while(gap > 1) {
            gap/=2;
            insertSortFun(arr, begin, end, gap);
        }
    }
    private static void insertSortFun(int[] arr, int begin, int end, int gap) {
        for(int i = begin + gap; i<=end; i++) {
            int j = i-gap;
            int tmp = arr[i];
            for(; j>=begin; j -= gap) {
                if(arr[j] > tmp) {
                   arr[j+gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public static void selectSort(int[] arr, int begin, int end) {
        for(int i = begin; i<end; i++) {
            int min = arr[i], minIndex = i;
            for(int j = i+1; j<=end; j++) {
                if(arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }


    public static void selectSort2(int[] arr, int begin, int end) {
        for(int i = begin, j = end; i<j; i++, j--) {
            int min = arr[i], minIndex = i;
            int max = arr[j], maxIndex = j;
            for(int k = i+1; k<j; k++) {
                if(arr[k] < min) {
                    min = arr[k];
                    minIndex = k;
                }
                if(arr[k] > max) {
                    max = arr[k];
                    maxIndex = k;
                }
            }

            swap(arr, i, minIndex);
            if(maxIndex == i) {
                maxIndex = minIndex;
            }
            swap(arr, j, maxIndex);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

   public static void heapSort(int[] arr) {
        createBigHeap(arr);

        int end = arr.length-1;
        while(end >= 0) {
            swap(arr, 0, end);

            shiftDown(arr, 0, end);
            end--;
        }
   }
   private static void createBigHeap(int[] arr) {
        int parent = (arr.length-1-1)/2;
        while(parent >= 0) {
            shiftDown(arr, parent, arr.length);
            parent--;
        }
   }
   private static void shiftDown(int[] arr, int parent, int end) {
       int child = parent * 2 + 1;
       while(child < end) {
           if(child+1 < end && arr[child+1] > arr[child]) {
               child++;
           }
           if(arr[parent] < arr[child]) {
               swap(arr, parent, child);
               parent = child;
               child = parent * 2 + 1;
           }else {
               break;
           }
       }
   }

   public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i<n-1; i++) {
            for(int j = 0; j<n-i-1; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
   }

   public static void quickSort(int[] arr, int begin, int end) {
        if(begin >= end) return;
        int pivot = partitionHoare(arr, begin, end);
        quickSort(arr, begin, pivot-1);
        quickSort(arr, pivot + 1, end);
   }

    private static int partitionHoare(int[] arr, int begin, int end) {
        int key = arr[begin];
        int left = begin, right = end;
        while(left < right) {
            //寻找比key小的数
            while(left < right && arr[right] >= key) {
                right--;
            }
            //寻找比key大的数
            while(left < right && arr[left] <= key) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, begin, left);
        return left;
    }

    public static void mergeSort(int[] arr, int begin, int end) {
        if(begin >= end) return;
        int mid = (begin + end) / 2;
        mergeSort(arr, begin, mid);
        mergeSort(arr, mid+1, end);

        merge(arr, begin, mid, end);
    }

    private static void merge(int[] arr, int begin, int mid, int end) {
        int s1 = begin, e1 = mid;
        int s2 = mid+1, e2 = end;
        int[] tmp = new int[end - begin + 1];
        int cur = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] <= arr[s2]) {
                tmp[cur++] = arr[s1++];
            }else {
                tmp[cur++] = arr[s2++];
            }
        }
        while(s1 <= e1) {
            tmp[cur++] = arr[s1++];
        }
        while(s2 <= e2) {
            tmp[cur++] = arr[s2++];
        }
        for(int i = begin; i<=end; i++) {
            arr[i] = tmp[i-begin];
        }
    }

    public static void mergeSortNor(int[] arr) {
        int gap = 1; //每组有几个数据
        while(gap < arr.length) {
            for(int i = 0; i<arr.length; i = i + gap*2) {
                int left = i;
                int mid = left + gap-1;
                int right = mid + gap;
                if(mid >= arr.length) {
                    mid = arr.length-1;
                }
                if(right >= arr.length) {
                    right = arr.length-1;
                }
                merge(arr, left, mid, right);
            }

            gap *= 2;
        }
    }

}
